class Solution:
    def wordBreak(self, s: str, wordDict: list) -> bool:
        if not wordDict:
            return False
        # 后续搜索时没有必要搜索所有长度,只需要搜索从字典中字符最短长度到最大长度的字符串就行了
        # 其实这里还可以优化,用集合保存所有值,后续遍历集合就可以
        max_length, min_length = 0, len(wordDict[0])
        for word in wordDict:
            max_length = max(max_length, len(word))
            min_length = min(min_length, len(word))
        # 转换成集合搜索比较快;动态规划的列表第一个默认是True,
        # 后面默认是False,第一个是True表示空的字符应该认为可以被分割
        word_set, res_list = set(wordDict), [not i for i in range(len(s)+1)]
        # 这里i不是直接的位置,而是位置+1,因为还有一个空的
        for i in range(1, len(s)+1):
            for j in range(min_length, max_length+1):
                # 小于0了注意别再处理了
                if i - j < 0:
                    break
                # 如果某个串在wordDict里,并且这个串开头是True,就说明到这个位置是可分割的
                # 还是要注意因为i是加过1的,所以索引容易弄错
                if s[i-j:i] in word_set and res_list[i-j]:
                    res_list[i] = True
                    break
        return res_list[-1]


a = Solution()
print(a.wordBreak(s="leetcode", wordDict=["leet", "code"]))
print(a.wordBreak(s="applepenapple", wordDict=["apple", "pen"]))
print(a.wordBreak(s="catsandog", wordDict=["cats", "dog", "sand", "and", "cat"]))
print(a.wordBreak(s="catsandog", wordDict=[]))
